package swordoffer.offer68_2;

import java.util.*;

public class HashMapSolution {
    /*
        算法思想：
            从p和q开始，向上遍历，遇到第一个的公共节点就是最近公共祖先。

            下面采用BFS进行向下遍历，当两个节点都找到遍历停止。
            利用哈希表来记录向上过程需要使用的父节点
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //记录父节点
        Map<TreeNode, TreeNode> record = new HashMap<>();
        //利用队列进行BFS
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        //root节点的父节点为null
        record.put(root, null);

        //直到两个节点都找到，结束循环
        while(!record.containsKey(p) || !record.containsKey(q)){
            TreeNode cur = queue.poll();
            if(cur.left != null){
                queue.offer(cur.left);
                record.put(cur.left, cur);
            }
            if(cur.right != null){
                queue.offer(cur.right);
                record.put(cur.right, cur);
            }
        }
        //利用散列表找公共节点
        HashSet<TreeNode> set = new HashSet<>();

        //从下到上遍历p节点，记录沿途节点
        while(p != null){
            set.add(p);
            p = record.get(p);
        }

        //从下到上遍历q节点，第一个重复节点就是最近公共祖先
        while(!set.contains(q)){
            q = record.get(q);
        }
        return q;
    }
}
